1. Field of the Invention
The present invention relates to computer networks and, more specifically, to computer networks configured to virtually associate different network segments.
2. Background Information
A computer network typically comprises a plurality of interconnected entities. An entity may consist of any network device, such as a server or end station, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs are interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (“WAN”) or intranet that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “switching” function between two or more LANs or end stations. Typically, the bridge is a computer and includes a plurality of ports that are coupled via LANs either to other bridges, or to end stations, such as routers or host computers. Ports used to couple bridges to each other are generally referred to as a trunk ports, whereas ports used to couple bridges to end stations are generally referred to as access ports. The bridging function includes receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to one or more receiving entities.
Bridges typically learn which destination port to use in order to reach a particular entity by noting on which source port the last message originating from that entity was received. This information is then stored in a block of memory referred to as a filtering database. Thereafter, when a message addressed to a given entity is received on a source port, the bridge looks up the entity in its filtering database and identifies the appropriate destination port to reach that entity. If no destination port is identified in the filtering database, the bridge floods the message out all ports, except the port on which the message was originally received. Messages addressed to broadcast or multicast addresses are also flooded.
Spanning Tree Algorithm
To avoid the formation of loops, most bridges and switches execute a spanning tree protocol which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The IEEE has promulgated a standard (IEEE Std. 802.1D-1998™ M) that defines a spanning tree protocol to be executed by 802.1D compatible devices. In general, by executing the 802.1D spanning tree protocol, bridges elect a single bridge within the bridged network to be the “root” bridge. The 802.1D standard takes advantage of the fact that each bridge has a unique numerical identifier (bridge ID) by specifying that the Root Bridge is the bridge with the lowest bridge ID. In addition, for each LAN coupled to any bridge, exactly one port (the “Designated port”) on one bridge (the “Designated Bridge”) is elected. The Designated Bridge is typically the one closest to the Root Bridge. All ports on the Root Bridge are Designated Ports, and the Root Bridge is the Designated Bridge on all the LANs to which it has ports. Each non-Root Bridge also selects one port from among its non-Designated Ports (its “Root Port”) which gives the lowest cost path to the Root Bridge. The Root Ports and Designated Ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto LANs interconnecting the bridges and end stations of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames will not be forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a disabled state.
To obtain the information necessary to run the spanning tree protocol, bridges exchange special messages called configuration bridge protocol data unit (BPDU) messages or simply BPDUs. BPDUs carry information, such as assumed root and lowest root path cost, used in computing the active topology. More specifically, upon start-up, each bridge initially assumes itself to be the Root Bridge and transmits BPDUs accordingly. Upon receipt of a BPDU from a neighboring device, its contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge in memory. If the information from the received BPDU is “better” than the stored information, the bridge adopts the better information and uses it in the BPDUs that it sends (adding the cost associated with the receiving port to the root path cost) from its ports, other than the port on which the “better” information was received. Although BPDUs are not forwarded by bridges, the identifier of the Root Bridge is eventually propagated to and adopted by all bridges as described above, allowing them to select their Root Port and any Designated Port(s).
In order to adapt the active topology to changes and failures, the Root Bridge periodically (e.g., every hello time) transmits BPDUs. In response to receiving BPDUs on their Root Ports, bridges transmit their own BPDUs from their Designated Ports, if any. Thus, BPDUs are periodically propagated throughout the bridged network, confirming the active topology. As BPDU information is updated and/or timed-out and the active topology is re-calculated, ports may transition from the blocking state to the forwarding state and vice versa. That is, as a result of new BPDU information, a previously blocked port may learn that it should be in the forwarding state (e.g., it is now the Root Port or a Designated Port).
Virtual Local Area Networks
A computer network may also be segregated into a series of logical network segments. For example, U.S. Pat. No. 5,394,402, issued on Feb. 28, 1995 to Ross (the “'402 Patent”), which is hereby incorporated by referenced in its entirety, discloses an arrangement for associating any port of a bridge with any particular segregated network group. Specifically, according to the '402 Patent, any number of physical ports of a particular bridge may be associated with any number of groups within the bridge by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. More specifically, Ross discloses a bridge or hub that associates VLAN designations with at least one local port and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each local port is stored in a memory portion of the bridge such that every time a message is received by the bridge on a local port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the local port where the message originated. In addition to the '402 patent, the IEEE has issued a standard for Virtual Bridged Local Area Networks, IEEE Std. 802.1Q-1998.
In many cases, it may be desirable to interconnect a plurality of these bridges in order to extend the VLAN associations of ports in the network. Ross, in fact, states that an objective of his VLAN arrangement is to allow all ports and entities of the network having the same VLAN designation to exchange messages by associating a VLAN designation with each message. Thus, those entities having the same VLAN designation function as if they are all part of the same LAN. Message exchanges between parts of the network having different VLAN designations are specifically prevented in order to preserve the boundaries of each VLAN segment. The IEEE Std. 802.1Q-1998 specification standard, for example, calls for the addition of a VLAN Identifier (VID) field to the header of network messages. The VID field may be loaded with a numeric value (0-4095) corresponding to the message's VLAN designation. For administrative convenience, each VLAN designation is often associated with a different color, such as red, blue, green, etc.
GVRP and VTP
A network that contains a number of VLANs may find it necessary for each bridge to maintain up-to-date information about which VLANs are accessible on which ports. Such information can be used to prevent messages associated with a given VLAN designation from being sent into areas of the network in which there are no members of the VLAN designation. To disseminate information across computer networks, the IEEE has developed the Generic Attribute Registration Protocol (GARP) as part of the IEEE 802.1D standard. A variation of GARP specially adopted for VLAN registration is the GARP VLAN Registration Protocol (GVRP) described in the IEEE Std. 802.1Q-1998 specification standard. Similarly, Cisco Systems, Inc of San Jose, Calif. has developed the VLAN Trunk Protocol (VTP) for internetwork communication and has created a VTP Pruning Protocol Extension specifically adapted to provide registration information used in restricting traffic. Both GVRP and VTP Pruning operate in software and follow a similar principle of “global information transmitted locally” in which each bridge transmits a complete copy of its current VLAN membership knowledge to its neighbors.
Both protocols include a control application associated with each port of a bridge in a LAN. The control application issues communications (declarations) that contain join (registration) and leave (deregistration) commands for membership in VLANs. Registration and deregistration commands contain information identifying the VLAN designations that the transmitting bridge needs to receive for its own ports as well as the ports of the bridges located “behind” or “downstream” of the transmitting bridge. In both protocols, a declaration may be issued in response to any of a number of events, such as an idle timer or a user initiated VLAN assignment. Declarations are only transmitted to adjacent or neighboring bridges. They are not forwarded. When a neighboring bridge receives a declaration, it creates or updates the Dynamic VLAN Registration Entries in its Port State vector, which is part of its filtering database, to indicate any new VLANs it must transmit. Further, any changes in the bridge's Dynamic VLAN Registration Entries causes the bridge to transmit declarations to its neighbors, which then transmit declarations to their neighbors, and so on, until the new the VLAN configuration is known throughout the network.
Both GVRP and VTP Pruning share a number of shortcomings. First, each bridge must include in its declarations a list of VLANs that includes both those specifically assigned to the bridge as well as those VLANs reachable “behind” the bridge. Assembling and updating this list requires repeated computation and processing. Second, bridges must calculate and transmit a different declaration containing a different VLAN registration and deregistration list on each of its ports. Otherwise, a bridge might indicate a need to receive messages associated with a given VLAN when, in fact, no such need exists. Finally, the prior art methods introduce significant delay in converging to an overall result. That is, when a new VLAN is needed at a particular bridge, there is considerable delay before the need is universally known throughout the network. This delay is due, in part, to the processing requirements at each bridge before the need can be propagated through the network. There is little opportunity to employ parallel processors to compute the declarations, as the declaration transmitted on each port depends on information received from all other ports on the bridge.
Thus, a need exits for a VLAN pruning protocol that consumes less overhead and converges quickly.